SPARQL Well-Designed Query Containment Benchmark: benchmark
This benchmark contains queries taken either from third-party benchmarks such as the Berlin Benchmark or that we have automatically generated. Queries in the Berlin Benchmark are based on the specific requirements of a real world use case. The following queries emulate the search and navigation pattern of a consumer looking for a product. In a real world setting, such a query sequence could for instance be executed by a shopping portal which is used by consumers to find products and sales offers [1] C. Bizer and A. Schultz. The Berlin SPARQL Benchmark.
We report on experimental results obtained with our own solver implementation for K-solver with multiple modilities, which is based on a classic tableau method [2] G. Pan, U. Sattler, and M. Y. Vardi. Bdd-based decision procedures for the modal logic k. It is implemented in Java.
We also report on results obtained with the MSPASS solver which decides K with multiple modilities using a completely different approach. MSPASS is an enhancement of the first-order theorem prover SPASS [3] U. Hustadt and R. A. Schmidt. Mspass: Modal reasoning by translation and first-order resolution. It is implemented in ANSI C.
We compare the results that we obtain with our logical approach using these two solvers with the results obtained with SPARQL-Algebra: an implementation of the SPARQL query subsumption and equivalence tests found in [4] A. Letelier, J. Perez, R. Pichler, and S. Skritek. Static analysis and optimization of semantic web queries.
The queries Q1a and Q1b have been obtained by removing some triple patterns from the Query 1 of the Berlin Benchmark in order to test a simple case of containment.
The query Q2a finds products for a given set of generic features and it is taken from the Berlin Benchmark (Query 1). Queries Q2b and Q2c are obtained by replacing a variable of the query Q2a with a specific value and by removing a triple pattern from Q2a.
The query Q3a find products having some features. This query is equal to the Query 3 of the Berling Benchmark. Queries Q3b and Q3c are obtained by removing a triple pattern that express a mandatory or an optional feature of the product, respectively.
The query Q4a and Q4b are obtained from the Query 2 of The Berlin Benchmark. These queries are used to check containment in presence of multiple optional matching.
The querier Q5a and Q5b are obtained from the Query 7 of the Berlin Benchmark. These queries are used to check containment in presence of a nested levels of optional operators.
Q1a ⊑ Q1b : true
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdfs:type> ?type .
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
}
Q1b ⊑ Q1a : false
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdfs:type> ?type .
}
Q2a ⊑ Q2b : false
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <bsbm:productPropertyNumeric1> ?value1 .
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <bsbm:productPropertyNumeric1> <foaf:Value1> .
}
Q2b ⊑ Q2a : true
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <bsbm:productPropertyNumeric1> <foaf:Value1>
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <bsbm:productPropertyNumeric1> ?value1 .
}
Q2a ⊑ Q2c : true
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:producteature> <foaf:ProductFeature1> .
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <bsbm:productPropertyNumeric1> ?value1 .
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
?product <bsbm:productFeature> <foaf:ProductFeature2> .
}
Q2c ⊑ Q2a : false
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
?product <bsbm:productFeature> <foaf:ProductFeature2> .
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:producteature> <foaf:ProductFeature1> .
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <bsbm:productPropertyNumeric1> ?value1 .
}
Q3a ⊑ Q3b : true
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
OPTIONAL {
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <rdfs:label> ?testVar.
}
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
OPTIONAL {
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <rdfs:label> ?testVar.
}
}
Q3b ⊑ Q3a : false
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
OPTIONAL {
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <rdfs:label> ?testVar.
}
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
OPTIONAL {
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <rdfs:label> ?testVar.
}
}
Q3a ⊑ Q3c : true
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
OPTIONAL {
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <rdfs:label> ?testVar.
}
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
OPTIONAL {
?product <bsbm:productFeature> <foaf:ProductFeature2> .
}
}
Q3c ⊑ Q3a : false
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
OPTIONAL {
?product <bsbm:productFeature> <foaf:ProductFeature2> .
}
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
?product <rdfs:label> ?label .
?product <rdf:a> <foaf:ProductType> .
?product <bsbm:productFeature> <foaf:ProductFeature1> .
OPTIONAL {
?product <bsbm:productFeature> <foaf:ProductFeature2> .
?product <rdfs:label> ?testVar.
}
}
Q4a ⊑ Q4b : true
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
<foaf:ProductXYZ> <rdfs:comment> ?comment .
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyTextual4> ?propertyTextual4 }
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyTextual5> ?propertyTextual5 }
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyNumeric4> <foaf:Value1> }
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
<foaf:ProductXYZ> <rdfs:comment> ?comment .
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyTextual4> ?propertyTextual4 }
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyTextual5> ?propertyTextual5 }
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyNumeric4> ?propertyNumeric6 }
}
Q4b ⊑ Q4a : false
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
<foaf:ProductXYZ> <rdfs:comment> ?comment .
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyTextual4> ?propertyTextual4 }
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyTextual5> ?propertyTextual5 }
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyNumeric4> ?propertyNumeric6 }
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
<foaf:ProductXYZ> <rdfs:comment> ?comment .
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyTextual4> ?propertyTextual4 }
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyTextual5> ?propertyTextual5 }
OPTIONAL { <foaf:ProductXYZ> <bsbm:productPropertyNumeric4> <foaf:Value1> }
}
Q5a ⊑ Q5b : false
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
OPTIONAL {
?offer <bsbm:product> <foaf:ProductXYZ> .
?offer <bsbm:price> ?price .
}
OPTIONAL {
?review <bsbm:reviewFor> <foaf:ProductXYZ> .
OPTIONAL { ?review <bsbm:rating1> ?rating1 . }
OPTIONAL { ?review <bsbm:rating2> ?rating2 . }
}
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
OPTIONAL {
?offer <bsbm:product> <foaf:ProductXYZ> .
?offer <bsbm:price> ?price .
}
OPTIONAL {
?review <bsbm:reviewFor> <foaf:ProductXYZ> .
OPTIONAL { ?review <bsbm:rating1> ?rating1 . }
}
}
Q5b ⊑ Q5a : true
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
OPTIONAL {
?offer <bsbm:product> <foaf:ProductXYZ> .
?offer <bsbm:price> ?price .
}
OPTIONAL {
?review <bsbm:reviewFor> <foaf:ProductXYZ> .
OPTIONAL { ?review <bsbm:rating1> ?rating1 . }
}
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
OPTIONAL {
?offer <bsbm:product> <foaf:ProductXYZ> .
?offer <bsbm:price> ?price .
}
OPTIONAL {
?review <bsbm:reviewFor> <foaf:ProductXYZ> .
OPTIONAL { ?review <bsbm:rating1> ?rating1 . }
OPTIONAL { ?review <bsbm:rating2> ?rating2 . }
}
}
Q5a ⊑ Q5c : false
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
OPTIONAL {
?offer <bsbm:product> <foaf:ProductXYZ> .
?offer <bsbm:price> ?price .
}
OPTIONAL {
?review <bsbm:reviewFor> <foaf:ProductXYZ> .
OPTIONAL { ?review <bsbm:rating1> ?rating1 . }
OPTIONAL { ?review <bsbm:rating2> ?rating2 . }
}
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
OPTIONAL {
?review <bsbm:reviewFor> <foaf:ProductXYZ> .
OPTIONAL { ?review <bsbm:rating1> ?rating1 . }
OPTIONAL {
?review <bsbm:rating2> ?rating2 .
OPTIONAL {?offer <bsbm:price> ?price .}
}
}
}
Q5c ⊑ Q5a : false
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
OPTIONAL {
?review <bsbm:reviewFor> <foaf:ProductXYZ> .
OPTIONAL { ?review <bsbm:rating1> ?rating1 . }
OPTIONAL {
?review <bsbm:rating2> ?rating2 .
OPTIONAL {?offer <bsbm:price> ?price .}
}
}
}
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>
PREFIX foaf: <http://xmlns.com/foaf/0.1/>
PREFIX bsbm: <http://www4.wiwiss.fu-berlin.de/bizer/bsbm/v01/vocabulary/>
PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
SELECT *
WHERE {
<foaf:ProductXYZ> <rdfs:label> ?label .
OPTIONAL {
?offer <bsbm:product> <foaf:ProductXYZ> .
?offer <bsbm:price> ?price .
}
OPTIONAL {
?review <bsbm:reviewFor> <foaf:ProductXYZ> .
OPTIONAL { ?review <bsbm:rating1> ?rating1 . }
OPTIONAL { ?review <bsbm:rating2> ?rating2 . }
}
}